package com.leetcode.study;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/498204367/
 *
 * 在排序数组中查找元素的第一个和最后一个位置
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 *
 * 提示：
 *
 * 0 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * nums 是一个非递减数组
 * -10^9 <= target <= 10^9
 *
 */
public class L34 {

    public static void main(String[] args) {

        int[] array = {1, 3, 5, 5, 5, 8, 10};

        System.out.println(Arrays.toString(searchRange(array, 5)));

    }


    public static int[] searchRange(int[] nums, int target) {
        int[] ints = new int[2];

        ints[0] = searchMostLeft(nums, target);
        ints[1] = searchMostRight(nums, target);

        return ints;
    }


    /**
     * 返回目标值在数组中最左边的索引值
     * [1,3,5,5,7,8,10] 给定5 返回索引下标2，给定6就返回-1
     * @param nums
     * @param target
     * @return 找到返回目标值最左索引
     *         找不到返回-1
     */
    public static int searchMostLeft(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        int temp = -1;
        while (i <= j) {
            int mid = (i + j) >>> 1;

            if (target < nums[mid]) {
                j = mid - 1;

            }
            else if (nums[mid] < target) {
                i = mid + 1;
            }
            else {
                temp = mid;
                // 因为找的是最左边索引，所以要继续缩小右边界
                j = mid - 1;
            }
        }

        return temp;
    }

    /**
     * 返回目标值在数组中最左边的索引值
     * [1,3,5,5,7,8,10] 给定5 返回索引下标2，给定6就返回3
     * @param nums
     * @param target
     * @return 返回 >= target的最左索引
     */
    public static int searchMostLeft1(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        while (i <= j) {
            int mid = (i + j) >>> 1;

            if (target <= nums[mid]) {
                j = mid - 1;

            }
            //else if (nums[mid] < target) {
            //    i = mid + 1;
            //}
            //else {
            //    // 因为找的是最左边索引，所以要继续缩小右边界
            //    j = mid - 1;
            //} 这段等价于下面的else{}
            else {
                i = mid + 1;
            }
        }

        return i;
    }


    /**
     * 返回重复值在数组中最右边的索引值
     * [1,3,5,5,5,8,10] 给定5 返回索引下标3，给定6就返回-1
     * @param nums
     * @param target
     * @return 找到返回目标值最右索引
     *         找不到返回-1
     */
    public static int searchMostRight(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        int temp = -1;

        while (i <= j) {
            int mid = (i + j) >>> 1;

            if (target < nums[mid]) {
                j = mid - 1;

            }
            else if (nums[mid] < target) {
                i = mid + 1;
            }
            else {
                // 因为找的是最右边索引，所以要继续缩小右边界
                temp = mid;
                i = mid + 1;
            }
        }

        return temp;
    }

    /**
     * 返回重复值在数组中最右边的索引值
     * [1,3,5,5,5,8,10] 给定5 返回索引下标3，给定6就返回-1
     * @param nums
     * @param target
     * @return 返回 <= target的最右索引
     */
    public static int searchMostRight1(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        while (i <= j) {
            int mid = (i + j) >>> 1;

            if (target < nums[mid]) {
                j = mid - 1;

            }
            else if (nums[mid] <= target) {
                i = mid + 1;

            }
            //else {
            //    // 因为找的是最右边索引，所以要继续缩小右边界
            //    i = mid + 1;
            //}
        }

        return i - 1;
    }


}
